﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Security.Cryptography;

namespace ThresholdModeling
{
    public class Cryptography
    {
        public static int BezoutAlgorithm_gcd(int a, int b, ref int x, ref int y)
        {
            int gcd = 1; //ax + by = d
            if (a < 0 || b < 0)
                return 0;
            int max = (a >= b) ? a : b;
            int min = (a < b) ? a : b;

            if (min == 0)
            {
                gcd = a;
                x = 1; y = 1;
            }
            else
            {
                int x2 = 1;
                int x1 = 0;
                int y2 = 0;
                int y1 = 1;
                int q, r;
                while (b > 0)
                {
                    q = a / b; r = a - q * b; x = x2 - q * x1; y = y2 - q * y1;
                    a = b; b = r; x2 = x1; x1 = x; y2 = y1; y1 = y;
                }
                gcd = a;
                x = x2; y = y2;
            }


            return gcd;
        }

        public static bool CheckRelativePrime(int a, int b)
        {
            bool isRelative = false;
            int x, y;
            x = y = 0;
            int gcd = BezoutAlgorithm_gcd(a, b, ref x, ref y);
            if (gcd == 0)
                return false;
            if (gcd == 1)
                isRelative = true;
            return isRelative;
        }

        public static bool CheckRelativePrimeWithArray(List<int> src, int a)
        {
            for (int i = 0; i < src.Count; i++)
            {
                if (!CheckRelativePrime(src[i], a))
                    return false;
            }
            return true;
        }

        //Find the inverse of a mod m, denoted by (a^-1 mod m)
        //if a is larger than m then calculate I = a % m
        //then find the inverse of I mod m
        //Algorithm no 1.45 in "Giao trinh ma hoa thong tin"
        public static int ModInverseIn_Zm(BigInteger a, int m)
        {
            int baseOfMod;
            int inverse = -1;
            if (a > m)
                baseOfMod = (int)(a % m);
            else
                baseOfMod = (int)a;

            int x, y;
            x = y = 0;
            int gcd = BezoutAlgorithm_gcd(baseOfMod, m, ref x, ref y);
            if (gcd > 1) //Non-existed a^-1
                return -1;
            if (gcd == 1)
            {
                int mod = x % m;
                if (mod < 0)
                    mod = m + mod;
                inverse = mod;
            }
            return inverse;
        }

        public static int ModInverseIn_Zm(int a, int m)
        {
            int baseOfMod;
            int inverse = -1;
            if (a > m)
                baseOfMod = a % m;
            else
                baseOfMod = a;

            int x, y;
            x = y = 0;
            int gcd = BezoutAlgorithm_gcd(baseOfMod, m, ref x, ref y);
            if (gcd > 1) //Non-existed a^-1
                return -1;
            if (gcd == 1)
            {
                int mod = x % m;
                if (mod < 0)
                    mod = m + mod;
                inverse = mod;
            }
            return inverse;
        }
        //Find all the Primes which are less than a given max threshold
        public static List<int> FindAllPrime(int minThreshold, int maxThreshold)
        {
            List<int> thresholds = new List<int>();
            try
            {
                for (int i = minThreshold; i < maxThreshold; i++)
                {
                    if (CheckPrime(i))
                        thresholds.Add(i);
                }
                return thresholds;
            }
            catch
            {
                return null;
            }
        }

        private static bool CheckPrime(int n)
        {
            if (n == 2)
                return true;
            for (int i = 2; i < n; i++)
            {
                if (n % i == 0)
                    return false;
            }
            return true;
        }

        public static String CreateHash(String src)
        {
            MD5 md5Hash = MD5.Create();
            byte[] data = md5Hash.ComputeHash(Encoding.UTF8.GetBytes(src));
            // Create a new Stringbuilder to collect the bytes
            // and create a string.
            StringBuilder sBuilder = new StringBuilder();

            // Loop through each byte of the hashed data 
            // and format each one as a hexadecimal string.
            for (int i = 0; i < data.Length; i++)
            {
                sBuilder.Append(data[i].ToString("x2"));
            }

            // Return the hexadecimal string.
            return sBuilder.ToString();
        }

        public static bool ExponentMod_Init(ref int k, ref int p)
        {
            Random r = new Random();
            List<int> primesLarge = FindAllPrime(10000, 11000);
            int lpIdx = r.Next(primesLarge.Count - 1);
            int pTemp = primesLarge[lpIdx];
            int kTemp = 0;
            int loopCount = 0;
            do
            {
                kTemp = r.Next(100, 999);
                loopCount++;
            }
            while (!CheckRelativePrime(kTemp, pTemp - 1) && loopCount <= 10000);

            if (loopCount <= 10000)
            {
                p = pTemp;
                k = kTemp;
                return true;
            }
            return false;
        }

        public static int ExponentCryptography_Decrypt(int digest, int key, int prime)
        {
            int message = 0;
            int inv_k = ModInverseIn_Zm(key, prime - 1);
            BigInteger inv_k_bigInt = BigIntegerManager.ConvertToBase_2(inv_k);
            message = inv_k_bigInt.ExponentMod_Base2(digest, prime);
            return message;
        }

        public static int ExponentCryptography_Encrypt(int message, int key, int prime)
        {
            int digest = 0;
            //int inv_k = ModInverseIn_Zm(key, prime - 1);
            BigInteger k_bigInt = BigIntegerManager.ConvertToBase_2(key);
            digest = k_bigInt.ExponentMod_Base2(message, prime);
            return digest;
        }
    }
}
